package com.wwz.didi;

import org.junit.Test;

/**
 * @description: 滴滴一面算法
 * 从两个升序的int数组中找出第k大的元素，
 * 输入：int[] arr1 = [7, 10], int[] arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
 * 要求时间复杂度<=O(n)，空间复杂度O(1)
 * @author: Sailor
 * @date: 2023-12-28 11:24:02
 */
public class Findk {
    @Test
    public void test() {
        System.out.println(findk(new int[]{7, 10}, new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}, 6));
    }

    public int findk(int[] arr1, int[] arr2, int k) {
        int a = arr1.length - 1;
        int b = arr2.length - 1;
        while (a >= 0 || b >= 0) {
            if (a >= 0 && b >= 0 && arr1[a] >= arr2[b]) {
                a--;
                k--;
                if (k == 0) {
                    return arr1[++a];
                }
            }
            if (a >= 0 && b >= 0 && arr1[a] <= arr2[b]) {
                b--;
                k--;
                if (k == 0) {
                    return arr2[++b];
                }
            }
            if (a >= 0 && b<=0) {
                return arr1[a - k];
            }
            if (b >= 0 && a<=0) {
                return arr2[b - k];
            }
        }
        return arr1[k];
    }
}
